package cn.yuemouren.tree.trie.leetcode;

import java.util.TreeMap;

/**
 * @Author: Timi
 * @Description: TODO
 * @Date: 2020/7/11 16:47
 * @Version: v1.0
 */
public class ValidParenthesis_208 {

    private class Node {

        private boolean isLeaf;//是否是节点
        private TreeMap<Character, Node> next;//目前节点对应下面的节点

        public Node() {
            this(false);
        }

        public Node(boolean isLeaf) {
            this.isLeaf = isLeaf;
            this.next = new TreeMap<>();
        }
    }

    private Node root;//根节点
    /** Initialize your data structure here. */
    public ValidParenthesis_208() {
        this.root = new Node();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        addRecursive(word,0,root);
    }

    private void addRecursive(String word, int index, Node cur){
        if (index == word.length()){
            if(!cur.isLeaf){
                cur.isLeaf = true;
            }
            return;
        }
        if(null == cur.next.get(word.charAt(index))){
            cur.next.put(word.charAt(index),new Node());
        }
        cur = cur.next.get(word.charAt(index));
        addRecursive(word,++index,cur);
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        return containsRecursive(word,0,root);
    }

    public boolean containsRecursive(String word, int index, Node cur){
        if(index == word.length()){
            return cur.isLeaf;
        }
        if(null == cur.next.get(word.charAt(index))){
            return false;
        }
        cur = cur.next.get(word.charAt(index));
        return containsRecursive(word,++index,cur);
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return isPrefix(prefix,0,root);
    }

    private boolean isPrefix(String prefix, int index, Node cur) {
        if(prefix.length() == index){
            return true;
        }
        if(null == cur.next.get(prefix.charAt(index))){
            return false;
        }
        cur = cur.next.get(prefix.charAt(index));
        return isPrefix(prefix,++index,cur);
    }

    public static void main(String[] args) {
        ValidParenthesis_208 trie = new ValidParenthesis_208();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // 返回 true
        System.out.println(trie.search("app"));     // 返回 false
        System.out.println(trie.startsWith("app")); // 返回 true
        trie.insert("app");
        System.out.println(trie.search("app"));     // 返回 true
    }
}
